﻿#include<iostream>
#include<vector>
#include <algorithm>
using namespace std;

// 本题思想：通过双指针dest与cur对数组元素进行移动
// dest指针：始终指向当前第一个0的位置，用于维护非零元素应当插入的位置
// cur指针：遍历数组寻找非零元素，当找到非零元素时与dest位置的0进行交换

// 核心逻辑：
// 1. 当dest遇到0且cur遇到非零元素时，完成零与非零元素的交换，双指针同时推进
// 2. 当dest位置为非零元素时，说明该位置已被正确维护，dest单独向前推进寻找下一个0
// 3. 最终保证所有非零元素按原序排列在前，所有零被移动至数组末端

// d               d              d              d    
//   c                 c               c              c             
// 0 1 0 3 12 -> 1 0 0 3 12   1 3 0 0 12  -> 1 3 12 0 0

int main()
{
	vector<int> nums({ 0,1,0,3,12});
	int dest=0, cur=0;

	while(cur<nums.size())
	{
		if (nums[dest]==0&&nums[cur]!=0)
		{
			swap(nums[dest], nums[cur]);
			dest++, cur++;
		}
		else
		{
			if(nums[dest] != 0)
			{
				dest++;
			}
			cur++;
		}
	}
	for (const auto& e:nums )
	{
		cout << e << " ";
	}

}